package com.xj.util.tree.bplus2;

import java.util.AbstractMap;
import java.util.ArrayList;
import java.util.List;
import java.util.Map.Entry;

/**
 * User: bjxiajun
 * Date: 13-11-6
 * Time: 下午1:14
 */
public class Node {
    private Node parent;//父节点
    private Node previous;//前节点
    private Node next;//下一节点
    private List<Node> children;//子节点
    private List<Entry<Comparable, Object>> entries;//节点内容
    private boolean isLeaf;//是否为叶子节点
    private boolean isRoot; //是否为根节点
    private boolean findType = false;//是否使用二分法查找key应该插入的位置

    /**
     * 构造函数
     *
     * @param isLeaf 是否是叶子节点
     * @param order  节点数、关键词数
     */
    public Node(boolean isLeaf, int order) {
        this.isLeaf = isLeaf;
        entries = new ArrayList(order);
        if (!isLeaf) {
            children = new ArrayList(order);
        }
    }

    /**
     * 构造函数
     *
     * @param isLeaf 是否是叶子节点
     * @param isRoot 是否是根节点
     * @param order  节点数、关键词数
     */
    public Node(boolean isLeaf, boolean isRoot, int order) {
        this(isLeaf, order);
        this.isRoot = isRoot;
    }

    /**
     * 查寻
     *
     * @param key
     * @return
     */
    public Object get(Comparable key) {
        if (isLeaf) {
            int i = dichotomy(entries, key);
            if (i >= 0) {
                return entries.get(i).getValue();
            }
            return null;
        } else {
            int index = entries.size() > 1 ? 1 : 0;
            if (key.compareTo(entries.get(index).getKey()) < 0) {
                return children.get(0).get(key);
            } else if (key.compareTo(entries.get(entries.size() - 1).getKey()) >= 0) {
                return children.get(entries.size() - 1).get(key);
            } else {
                for (int i = index; i < entries.size(); i++) {
                    if (key.compareTo(entries.get(i).getKey()) >= 0 && key.compareTo(entries.get(i + 1).getKey()) < 0) {
                        return children.get(i).get(key);
                    }
                }
            }
        }
        return null;
    }

    /**
     * b+树的插入算法
     * 1、当最初插入关键字的时候，即根节点就是叶子节点，那么直接插入，假如插入后根节点的关键字数量大于m，那么需要分裂；
     * 2、寻找需要插入到的叶子节点，假如已经包含该关键字，报错，否则插入该关键字，查看关键字数量是否达到分裂条件，假如达到，则进行分裂操作。
     * 必须注意的是，我这里的b+树对于大小的判断是：第一个子树的关键字必然大于或等于父亲的第一个关键字，小于父亲第二个关键字，如此类推，
     * 网上的算法也有第一个子树的所有关键字都小于或等于父亲的第一个关键字这种。
     */
    public void insertOrUpdate(Comparable key, Object obj, BplusTree tree) {
        if (isLeaf) {//是否是叶子节点
            if (contains(key) || entries.size() < tree.getOrder()) {
                insert(key, obj, findType);
                if (parent != null) {
                    parent.refreshInsert(tree);
                }
            } else {
                insert(key, obj, findType);
                if (entries.size() > tree.getOrder() && next != null && next.getEntries().size() < tree.getOrder()) {
                    Entry entry = entries.get(entries.size() - 1);
                    entries.remove(entry);
                    next.getEntries().add(0, entry);
                    Node parent = next.getParent();
                    parent.refreshInsert(tree);
                } else {
                    Node right = new Node(true, tree.getOrder());
                    if (next != null) {
                        next.setPrevious(right);
                        right.setNext(next);
                    }
                    this.setNext(right);
                    right.setPrevious(this);
                    int leftSize = entries.size() - 2;
                    for (int i = 0; i < 2; i++) {
                        right.getEntries().add(entries.get(leftSize + i));
                    }
                    for (int i = 0; i < 2; i++) {
                        entries.remove(entries.size() - 1);
                    }
                    if (parent != null) {
                        int index = parent.getChildren().indexOf(this);
                        right.setParent(parent);
                        parent.getChildren().add(index + 1, right);
                        parent.refreshInsert(tree);
                    } else {
                        isRoot = false;
                        Node parent = new Node(false, true, tree.getOrder());
                        tree.setRoot(parent);
                        this.setParent(parent);
                        right.setParent(parent);
                        parent.getChildren().add(this);
                        parent.getChildren().add(right);
                        parent.refreshInsert(tree);
                    }
                }
            }
        } else {
            if (key.compareTo(entries.get(0).getKey()) <= 0) {
                children.get(0).insertOrUpdate(key, obj, tree);
            } else if (key.compareTo(entries.get(entries.size() - 1).getKey()) >= 0) {
                children.get(children.size() - 1).insertOrUpdate(key, obj, tree);
            } else {
                for (int i = 0; i < entries.size(); i++) {
                    if (entries.get(i).getKey().compareTo(key) <= 0 && entries.get(i + 1).getKey().compareTo(key) > 0) {
                        children.get(i).insertOrUpdate(key, obj, tree);
                        break;
                    }
                }
            }
        }
    }

    /**
     * 写入数据
     *
     * @param key
     * @param obj
     * @param boo 是否使用二分法进行查找插入的位置
     */
    protected void insert(Comparable key, Object obj, boolean boo) {
        if (boo) {
            dichotomyInsert(key, obj);
        } else {
            iterationInsert(key, obj);
        }
    }

    /**
     * 使用二分法查询插入位置
     * 写入内容，将关键词写入叶子节点
     *
     * @param key 关键词key
     * @param obj 内容
     */
    protected void dichotomyInsert(Comparable key, Object obj) {
        Entry<Comparable, Object> entry = new AbstractMap.SimpleEntry(key, obj);
        if (entries.size() == 0) {//当关键字个数为0时直接插入
            entries.add(entry);
            return;
        }
        if (entries.get(0).getKey().compareTo(key) > 0) {
            entries.add(0, entry);
        } else if (entries.get(entries.size() - 1).getKey().compareTo(key) < 0) {
            entries.add(entry);
        } else {
            int i = dichotomy(entries, key);
            if (i >= 0) {
                entries.get(i).setValue(obj);
            } else {
                i = -i - 1;
                entries.add(i, entry);
            }
        }
    }

    /**
     * 迭代查询插入位置
     * 写入内容，将关键词写入叶子节点
     *
     * @param key 关键词key
     * @param obj 内容
     */
    protected void iterationInsert(Comparable key, Object obj) {
        Entry<Comparable, Object> entry = new AbstractMap.SimpleEntry(key, obj);
        if (entries.size() == 0) {//当关键字个数为0时直接插入
            entries.add(entry);
            return;
        }
        for (int i = 0; i < entries.size(); i++) {
            if (entries.get(i).getKey().compareTo(key) == 0) {//已经存在此关键字 更新它的值
                entries.get(i).setValue(obj);
                return;
            } else if (entries.get(i).getKey().compareTo(key) > 0) {//当前值正序
                if (i == 0) {
                    entries.add(0, entry);
                    return;
                } else {
                    entries.add(i, entry);
                    return;
                }
            }
        }
        entries.add(entries.size(), entry);
    }

    /**
     * 二分法查找
     *
     * @param entries
     * @param key
     * @return
     */
    private int dichotomy(List<Entry<Comparable, Object>> entries, Comparable key) {
        int low = 0;
        int high = entries.size() - 1;
        while (low <= high) {
            int mid = (low + high) >>> 1;
            int cmp = entries.get(mid).getKey().compareTo(key);
            if (cmp < 0)
                low = mid + 1;
            else if (cmp > 0)
                high = mid - 1;
            else
                return mid;
        }
        return -(low + 1);
    }

    /**
     * 当插入新的数据后从新分配节点
     *
     * @param tree
     */
    protected void refreshInsert(BplusTree tree) {
        refresh(this, tree);
        if (children.size() > tree.getOrder()) {
            Node right = new Node(false, tree.getOrder());
            int leftSize = children.size() / 2;
            int rightSize = children.size() - leftSize;
            for (int i = 0; i < rightSize; i++) {
                Node node = children.get(leftSize + i);
                right.getChildren().add(node);
                right.getEntries().add(new AbstractMap.SimpleEntry(node.getEntries().get(0).getKey(), null));
                node.setParent(right);
            }
            for (int i = 0; i < rightSize; i++) {
                children.remove(children.size() - 1);
                entries.remove(entries.size() - 1);
            }
            if (parent != null) {//此节点本身还有父节点
                int index = parent.getChildren().indexOf(this);
                parent.getChildren().add(index + 1, right);
                right.setParent(parent);
                parent.refreshInsert(tree);
            } else {
                isRoot = false;
                Node parent = new Node(false, true, tree.getOrder());
                tree.setRoot(parent);
                this.setParent(parent);
                right.setParent(parent);
                parent.getChildren().add(this);
                parent.getChildren().add(right);
                parent.refreshInsert(tree);
            }
        }
    }

    /**
     * 当子节点发生改变时刷新父节点关键词
     */
    protected static void refresh(Node node, BplusTree tree) {
        if (node.getChildren().size() == node.getEntries().size()) {//子节点数和关键字数相同时将子节点的最小值更新给 父节点关键词
            for (int i = 0; i < node.getChildren().size(); i++) {
                Comparable key = node.getChildren().get(i).getEntries().get(0).getKey();
                if (node.getEntries().get(i).getKey().compareTo(key) != 0) {
                    node.getEntries().remove(i);
                    node.getEntries().add(i, new AbstractMap.SimpleEntry(key, null));
                    if (!node.isRoot()) {
                        refresh(node.getParent(), tree);
                    }
                }
            }//当子节点数比关键词数多时 要添加关键词
        } else if (node.isRoot() && node.getChildren().size() >= 2 || node.getChildren().size() >= tree.getOrder() / 2 && node.getChildren().size() >= 2) {
            node.getEntries().clear();
            for (int i = 0; i < node.getChildren().size(); i++) {
                Comparable key = node.getChildren().get(i).getEntries().get(0).getKey();
                node.getEntries().add(new AbstractMap.SimpleEntry(key, null));
                if (!node.isRoot()) {
                    refresh(node.getParent(), tree);
                }
            }
        }

    }

    /**
     * 删除节点后中间节点的更新
     */
    protected void updateRemove(BplusTree tree) {
        refresh(this, tree);
        if (entries.size() < tree.getOrder() / 2 || children.size() < 2) {
            if (isRoot) {
                if (children.size() >= 2) {// 如果是根节点并且子节点数大于等于2
                    return;
                } else {// 否则与子节点合并
                    Node root = children.get(0);
                    tree.setRoot(root);
                    root.setParent(null);
                    root.setPrevious(null);
                    root.setRoot(true);
                    this.setEntries(null);
                    this.setChildren(null);
                }
            } else {
                int currIdx = parent.getChildren().indexOf(this);
                int prevIdx = currIdx - 1;
                int nextIdx = currIdx + 1;
                Node previous = null;
                Node next = null;
                if (prevIdx >= 0) {
                    previous = parent.getChildren().get(prevIdx);
                }
                if (nextIdx < parent.getChildren().size()) {
                    next = parent.getChildren().get(nextIdx);
                }
                // 如果前节点子节点数大于M / 2并且大于2，则从其处借补
                if (previous != null && previous.getChildren().size() > tree.getOrder() / 2 && previous.getChildren().size() > 2) {
                    //将前叶子节点末尾节点添加到首位
                    Node borrow = previous.getChildren().get(previous.getChildren().size() - 1);
                    previous.getChildren().remove(borrow);
                    borrow.setParent(this);
                    this.getChildren().add(0, borrow);
                    refresh(previous, tree);
                    refresh(this, tree);
                    parent.updateRemove(tree);
                    // 如果后节点子节点数大于M / 2并且大于2，则从其处借补
                } else if (next != null && next.getChildren().size() > tree.getOrder() / 2 && next.getChildren().size() > 2) {
                    //后叶子节点首位添加到末尾
                    Node borrow = next.getChildren().get(0);
                    next.getChildren().remove(borrow);
                    next.setParent(this);
                    this.getChildren().add(borrow);
                    refresh(next, tree);
                    refresh(this, tree);
                    parent.updateRemove(tree);
                } else {// 否则需要合并节点
                    // 同前面节点合并
                    if (previous != null && (previous.getChildren().size() <= tree.getOrder() / 2 || previous
                            .getChildren().size() <= 2)) {
                        for (int i = previous.getChildren().size() - 1; i >= 0; i--) {
                            Node child = previous.getChildren().get(i);
                            this.getChildren().add(0, child);
                            child.setParent(this);
                        }
                        previous.setChildren(null);
                        previous.setEntries(null);
                        previous.setParent(null);
                        parent.getChildren().remove(previous);
                        refresh(this, tree);
                        parent.updateRemove(tree);
                    } else if (next != null && (next.getChildren().size() <= tree.getOrder() / 2 || next.getChildren().size() <= 2)) {
                        for (int i = 0; i < next.getChildren().size(); i++) {
                            Node child = next.getChildren().get(i);
                            children.add(child);
                            child.setParent(this);
                        }
                        next.setChildren(null);
                        next.setEntries(null);
                        next.setParent(null);
                        parent.getChildren().remove(next);
                        refresh(this, tree);
                        parent.updateRemove(tree);
                    }
                }
            }
        }
    }

    /**
     * B+树的删除有几种情形
     * 原则：
     * 1、所有的删除操作都是在叶子节点进行的，每次删除都请先定位相关叶子节点；
     * 2、必须保持b+树的原则，具体举例（以本文实现的B+树算法而言），除了根节点，所有节点的关键字数量必须大于或等于_min，
     * 小于或等于_m，当小于_min的时候，可以这样处理：
     * 2A、假如左右叶子节点有多余的关键字，可以向左右借；
     * 2B、假如左右节点没有，那么只能合并节点，然后递归。（这种情况是进行递归的唯一情况）。
     */
    public void remove(Comparable key, BplusTree tree) {
        //如果是叶子节点
        if (isLeaf) {
            //如果不包含该关键字，则直接返回
            if (!contains(key)) {
                return;
            }
            //如果既是叶子节点又是跟节点，直接删除
            if (isRoot) {
                remove(key);
            } else {
                if (entries.size() > (tree.getOrder() / 2) && entries.size() > 2) {
                    remove(key);
                } else {
                    //如果自身关键字数小于M / 2，并且前节点关键字数大于M / 2，则从其处借补
                    if (previous != null && previous.entries.size() > tree.getOrder() / 2 && previous.entries.size() >
                            2 && previous.getParent() == parent) {
                        int size = previous.getEntries().size();
                        Entry entry = previous.getEntries().get(size - 1);
                        previous.getEntries().remove(entry);
                        entries.add(0, entry);//添加到首位
                        remove(key);
                    } else if (next != null && next.getEntries().size() > tree.getOrder() / 2 && next.getEntries().size() > 2 && next
                            .getParent() == parent) {//如果自身关键字数小于M / 2，并且后节点关键字数大于M / 2，则从其处借补
                        Entry entry = next.getEntries().get(0);
                        next.getEntries().remove(entry);
                        entries.add(entry);//添加到末尾
                        remove(key);
                    } else {//否则需要合并叶子节点
                        //同前面节点合并
                        if (previous != null && (previous.getEntries().size() <= tree.getOrder() / 2 || previous.getEntries().size() <= 2) && previous.getParent() == parent) {
                            for (int i = previous.getEntries().size() - 1; i >= 0; i--) {
                                //从末尾开始添加到首位
                                entries.add(0, previous.getEntries().get(i));
                            }
                            remove(key);
                            previous.setParent(null);
                            previous.setEntries(null);
                            parent.getChildren().remove(previous);
                            if (previous.getPrevious() != null) {
                                Node temp = previous;
                                temp.getPrevious().setNext(this);
                                previous = temp.getPrevious();
                                temp.setPrevious(null);
                                temp.setNext(null);
                            } else {
                                tree.setHead(this);
                                previous.setNext(null);
                                previous = null;
                            }//同后面节点合并
                        } else if (next != null && (next.getEntries().size() <= tree.getOrder() / 2 || next.getEntries().size()
                                <= 2) && next.getParent() == parent) {
                            for (int i = 0; i < next.getEntries().size(); i++) {
                                //从首位开始添加到末尾
                                entries.add(next.getEntries().get(i));
                            }
                            remove(key);
                            next.setParent(null);
                            next.setEntries(null);
                            parent.getChildren().remove(next);
                            //更新链表
                            if (next.getNext() != null) {
                                Node temp = next;
                                temp.getNext().setPrevious(this);
                                next = temp.getNext();
                                temp.setPrevious(null);
                                temp.setNext(null);
                            } else {
                                next.setPrevious(null);
                                next = null;
                            }
                        }
                    }
                }
                parent.updateRemove(tree);
            }
        } else {//如果不是叶子节点
            int index = entries.size() > 1 ? 1 : 0;
            if (key.compareTo(entries.get(index).getKey()) < 0) {
                children.get(0).remove(key, tree);
            } else if (key.compareTo(entries.get(entries.size() - 1).getKey()) >= 0) {//如果key大于节点最右边的key，沿最后一个子节点继续搜索
                children.get(children.size() - 1).remove(key, tree);
                //否则沿比key大的前一个子节点继续搜索
            } else {
                for (int i = index; i < entries.size(); i++) {
                    if (entries.get(i).getKey().compareTo(key) <= 0 && entries.get(i + 1).getKey().compareTo(key) > 0) {
                        children.get(i).remove(key, tree);
                        break;
                    }
                }
            }
        }
    }

    /**
     * 判断key是否在数据集合内
     *
     * @param key
     * @return
     */
    protected boolean contains(Comparable key) {
        for (Entry<Comparable, Object> entry : entries) {
            if (entry.getKey().compareTo(key) == 0) {
                return true;
            }
        }
        return false;
    }

    /**
     * 删除节点
     */
    protected void remove(Comparable key) {
        int index = -1;
        for (int i = 0; i < entries.size(); i++) {
            if (key.compareTo(entries.get(i).getKey()) == 0) {
                index = i;
                break;
            }
        }
        if (index != -1) {
            entries.remove(index);
        }
    }

    public Node getParent() {
        return parent;
    }

    public void setParent(Node parent) {
        this.parent = parent;
    }

    public Node getPrevious() {
        return previous;
    }

    public void setPrevious(Node previous) {
        this.previous = previous;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public List<Node> getChildren() {
        return children;
    }

    public void setChildren(List<Node> children) {
        this.children = children;
    }

    public List<Entry<Comparable, Object>> getEntries() {
        return entries;
    }

    public void setEntries(List<Entry<Comparable, Object>> entries) {
        this.entries = entries;
    }

    public boolean isLeaf() {
        return isLeaf;
    }

    public void setLeaf(boolean leaf) {
        isLeaf = leaf;
    }

    public boolean isRoot() {
        return isRoot;
    }

    public void setRoot(boolean root) {
        isRoot = root;
    }

    public boolean isFindType() {
        return findType;
    }

    public void setFindType(boolean findType) {
        this.findType = findType;
    }
}